#include <iostream>
#include <array>
#include <queue>
#include <memory>

using std::cout;
using std::endl;
using std::queue;
using std::array;
using std::shared_ptr;
using std::make_shared;

struct Node{
    Node(int l, int w, shared_ptr<Node> p, bool i):weight(w), level(l), parent(p), isleft(i){}
    int weight; // 当前已选节点的总重量;
    int level; // 当前已选节点的层数
    shared_ptr<Node> parent;    // 当前已选节点的父节点
    bool isleft;    // 当前节点是否被选择
};

static int cw = 0;
static int bestw = 0;
queue<shared_ptr<Node>> que;
shared_ptr<Node> pNode;
shared_ptr<Node> bestNode;

void addLiveNode(int level, int weight, shared_ptr<Node> parent, bool isleft)
{
    que.push(make_shared<Node>(level, weight, parent, isleft));
    
    // 只有当前节点为叶子节点，并且总重量等于最大重量时，说明遍历完成了，将当前节点记录下来，方便查看选择了哪些节点
    if(level == 3 && weight == bestw){
        bestNode = que.back();
    }
}

template<size_t N>
int maxBound(array<int, N> &arr, int level)
{
    int ret = 0;
    for(int j{level + 1}; j < N; j++){
        ret += arr[j];
    }
    return ret;
}

template<size_t N>
void func(array<int, N> &arr, int c)
{
    shared_ptr<Node> smartP;
    int i = 0;
    while(i < N){
        if(cw + arr[i] <= c){
            if(cw + arr[i] > bestw){
                bestw = cw + arr[i];
            }

            addLiveNode(i + 1, cw + arr[i], pNode, true);
        } 

        if(maxBound(arr, i) + cw >= bestw){
            addLiveNode(i + 1, cw, pNode, false);
        }

        smartP = que.front();
        que.pop();

        i = smartP->level;
        cw = smartP->weight;
        pNode = smartP;
    }

    for(int j{N - 1}; j >= 0; j--){
        arr[j] = bestNode->isleft ? 1: 0;
        bestNode = bestNode->parent;
    }
}

int main(int args, char *argv[])
{
    array<int, 3> arr {12, 8, 15};
    func(arr, 27);
    cout << bestw << endl;
    for(int i: arr){
        cout << i << " ";
    }
    cout << endl;
    return 0;
}